package 剑指offer_leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * JZ26树的子结构
 */
public class 剑指Offer26_树的子结构 {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null || B==null)
            return false;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(A);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if(node.val==B.val){
                if(helper(node,B))
                    return true;
            }
            if(node.left!=null)
                q.offer(node.left);
            if(node.right!=null)
                q.offer(node.right);
        }
        return false;
    }

    boolean helper(TreeNode root1, TreeNode root2){
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        q1.offer(root1);
        q2.offer(root2);
        while(!q2.isEmpty()){
            TreeNode n1 = q1.poll();
            TreeNode n2 = q2.poll();
            if( n1==null || n1.val!=n2.val)
                return false;
            if(n2.left!=null){
                q1.offer(n1.left);
                q2.offer(n2.left);
            }
            if(n2.right!=null){
                q1.offer(n1.right);
                q2.offer(n2.right);
            }
        }
        return true;
    }
}
